package com.treeroot.linkedlist;

/**
 * 创建一个环形的单向链表
 */
public class CircleSingleLinkedList {
    /**
     * 创建一个first节点，当前没有编号
     */
    private Boy boyFirst = null;

    //添加节点，构建成一个环形的链表
    public void addBoy(int boyNumbers) {
        //1.效验
        if (boyNumbers < 1) {
            System.out.println("boyNumbers的值不正确");
        }
        //辅助指针，帮助构建环形链表
        Boy currentBoy = null;
        //2.for循环创建环形链表,从1号开始
        for (int i = 1; i <= boyNumbers; i++) {
            //3.根据编号创建节点
            Boy boy = new Boy(i);
            //如果是第一个小孩
            if (i == 1) {
                //让first指向第一个小孩
                boyFirst = boy;
                //构成环状
                boyFirst.setNext(boyFirst);
                //让currentBoy指向第一个小孩
                currentBoy = boyFirst;
            } else {
                //构成环状
                currentBoy.setNext(boy);
                //将最后一个节点的 next 指针指向了第一个节点
                boy.setNext(boyFirst);
                currentBoy = boy;
            }

        }
    }

    /**
     * 遍历当前环形链表
     */
    public void list() {
        //1.效验
        if (boyFirst == null) {
            System.out.println("链表为空");
        }
        //2. 创建辅助指针完成遍历
        Boy current = boyFirst;
        while (true) {
            System.out.println("小孩的编号为：" + current.getNo());
            //判断是否遍历完毕
            if (current.getNext() == boyFirst) {
                break;
            }
            //将current后移
            current = current.getNext();
        }
    }

    /**
     * 根据用户输入
     * 计算出圈的顺序
     *
     * @param startNo  从第几个小孩开始数数
     * @param countNum 数几下
     * @param nums     最初有多少小孩在圈中
     */
    public void cont(int startNo, int countNum, int nums) {
        //1.效验
        //boyFirst == null 说明没有任何小孩
        //startNo < 1 从第几个小孩开始数数
        //startNo > nums 从第几个小孩开始数数
        if (boyFirst.getNext() == null || startNo < 1 || startNo > nums) {
            System.out.println("参数输入有误，请重新输入");
        }
        //2.创建辅助指针完成遍历
        Boy helper = boyFirst;
        while (true) {
            //说明helper指向了最后一个节点
            if (helper.getNext() == boyFirst) {
                break;
            }
            //将helper后移
            helper = helper.getNext();
        }
        //将boyFirst和helper移动到开始数数的位置
        for (int i = 0; i < startNo - 1; i++) {
            boyFirst = boyFirst.getNext();
            helper = helper.getNext();
        }
        //当小孩报数时，让boyFirst和helper指针同时移动 m - 1 次,然后出圈
        //这里是一个循环操作，直到圈中只有一个节点才退出
        while (true) {
            //说明圈中只有一个节点
            if (helper == boyFirst) {
                break;
            }

            //让boyFirst和helper指针同时移动 countNum - 1 次,然后出圈
            for (int i = 0; i < countNum - 1; i++) {
                boyFirst = boyFirst.getNext();
                helper = helper.getNext();
                //这时boyFirst指向的节点，就是要出圈的小孩节点
            }
            System.out.println("小孩" + boyFirst.getNo() + "出圈");
            //这时将boyFirst指向的小孩节点出圈
            boyFirst = boyFirst.getNext();
            //将helper指向boyFirst的下一个节点
            helper.setNext(boyFirst);
        }
        System.out.println("最后留在圈中的小孩编号为：" + boyFirst.getNo());

    }

}
